The present invention is directed, in general, to packet routing systems and, more specifically, to a system for providing a seamless switchover from a primary packet routing device to a secondary packet routing device.
Information systems have evolved from centralized mainframe computer systems supporting a large number of users to distributed computer systems based on local area network (LAN) architectures. As the cost-to-processing-power ratios for desktop PCs and network servers have dropped precipitously, LAN systems have proved to be highly cost effective. As a result, the number of LANs and LAN-based applications has exploded.
A consequential development relating to the increased popularity of LANs has been the interconnection of remote LANs, computers, and other equipment into wide area networks (WANs) in order to make more resources available to users. However, a LAN backbone can transmit data between users at high bandwidth rates for only relatively short distances. In order to interconnect devices across large distances, different communication protocols have been developed. These include packet switching protocols, such as X.25, ISDN, frame relay, and ATM, among others.
Packet switching involves the transmission of data in packets through a network. Each block of end-user data that is to be transmitted is divided into packets. A unique identifier, a sequence number and a destination address are attached to each data packet. The packets are independent and may traverse the data network by different routes. The packets may incur different levels of propagation delay, or latency, caused by physical paths of different length. The packets may be held for varying amounts of delay time in packet buffers in intermediate switches in the network. The packets also may be switched through different numbers of packet switches as the packets traverse the network, and the switches may have unequal processing delays caused by error detection and correction.
As a result, the packets may arrive out-of-order at the destination node. However, the destination node uses the identification and sequencing information in each data packet to assemble the data packets back in the proper order before continuing to process the original end-user data block.
To enhance the reliability of a packet switched network, it is common practice to build the packet switches as redundant devices. Each packet switch contains a primary (also called xe2x80x9cmasterxe2x80x9d or xe2x80x9cactivexe2x80x9d) packet routing engine that ordinarily performs packet routing and a secondary (also called xe2x80x9cslavexe2x80x9d or xe2x80x9cstandbyxe2x80x9d) packet routing engine that takes over from the primary packet routing engine upon failure or upon the occurrence of certain selected events.
In such redundant architectures, the primary packet routing engine and the secondary packet routing engine receive and process the same inputs (incoming packets) in such a way that the secondary packet routing engine mirrors the behavior of the primary packet routing engine. However, only the primary packet routing engine is allowed to perform physical output on the outgoing packets. The secondary packet routing engine also produces the outgoing packets but the physical output is negated. This type of xe2x80x9chotxe2x80x9d secondary packet routing engine allows a switchover (failover) procedure to consist of a simple reversal of the output mechanism (i.e., the output of the primary packet routing engine is disabled and the output of the secondary packet routing engine is enabled).
This type of redundant architecture has basic flaws, however. The two packet routing engine may generate the same packets in the output, but without special synchronization mechanisms, the different I/O behavior of the packet routing engines may lead to differences in task scheduling. This, in turn, may produce a different output sequence from each packet routing engine. Also, even if the sequence is the same, the timing of the outputs may be different. In general, when multiple data streams are funneled through a packet engine, the overall message output sequence is not a deterministic function of the inputs, it varies instead with the load. Moreover, the timing of the actual output is not deterministic. In this configuration, a switchover consisting of a simple reversal of the output mechanismxe2x80x94disabling the output of the primary packet routing engine and enabling the output of the secondary packet routing enginexe2x80x94lead to packet losses and/or duplications.
There is therefore a need in the art for improved redundancy architecture for use in a packet routing device. In particular, there is a need for an improved redundant packet architecture that provides a smooth switchover from a primary packet routing engine to a secondary packet routing engine. More particularly, there is a need for a redundant packet architecture that enables a primary packet routing engine to be switched over to a secondary packet routing engine without the loss of data packets or the duplicate processing of data packets.
To address the above-discussed deficiencies of the prior art, it is a primary object.of the present invention to provide, for use in a packet switched network, a redundant switch comprising 1) a primary packet router capable of routing a first stream of data packets from an input interface to an output interface of the redundant switch; 2) a secondary packet router capable of routing a second stream of data packets corresponding to the first stream of data packets from the input interface to the output interface of the redundant switch; 3) a packet ID generator capable of attaching a unique identifier to each data packet in the first stream of data packets and attaching the unique identifier to each corresponding data packet in the second stream of data packets; and 4) a comparator capable of comparing a first unique identifier associated with a first data packet processed by the primary packet router with a second unique identifier associated with a second data packet associated with the secondary packet router, wherein the comparator, in response to a determination that the first and second unique identifiers match, is capable of causing the second data packet associated with the secondary packet router to be deleted. In some embodiments of the present invention, the comparator may be implemented as a specific-purpose comparator circuit. In other embodiment of the present invention, the comparator may be implemented as software executed by a processor, such as a packet router.
In one embodiment of the present invention, the secondary packet router comprises an outbound data packet queue capable of storing the second data packet.
In another embodiment of the present invention, the comparator is capable of causing the second data packet to be deleted from the outbound data packet queue.
According to still another embodiment of the present invention, the primary packet router comprises a first outbound data packet queue capable of storing the first data packet.
According to yet another embodiment of the present invention, the secondary packet router comprises a second outbound data packet queue capable of storing the second data packet and the comparator receives the first unique identifier from the first outbound data packet queue and receives the second unique identifier from the second outbound data packet queue.
According to a further embodiment of the present invention, the comparator is capable of causing the second data packet to be deleted from the second outbound data packet queue.
According to a still further embodiment of the present invention, the redundant switch further comprises a peripheral device coupled to the primary packet router, wherein the peripheral device is capable of receiving and storing the first data packet and the first unique identifier received from primary packet router.
According to a yet further embodiment of the present invention, the secondary packet router comprises an outbound data packet queue capable of storing the second data packet and the comparator receives the first unique identifier from the peripheral device and receives the second unique identifier from the outbound data packet queue and wherein the comparator is capable of causing the second data packet to be deleted from the outbound data packet queue.
The foregoing has outlined rather broadly the features and technical advantages of the present invention so that those skilled in the art may better understand the detailed description of the invention that follows. Additional features and advantages of the invention will be described hereinafter that form the subject of the claims of the invention. Those skilled in the art should appreciate that they may readily use the conception and the specific embodiment disclosed as a basis for modifying or designing other structures for carrying out the same purposes of the present invention. Those skilled in the art should also realize that such equivalent constructions do not depart from the spirit and scope of the invention in its broadest form.
Before undertaking the DETAILED DESCRIPTION, it may be advantageous to set forth definitions of certain words and phrases used throughout this patent document: the terms xe2x80x9cincludexe2x80x9d and xe2x80x9ccomprise,xe2x80x9d as well as derivatives thereof, mean inclusion without limitation; the term xe2x80x9cor,xe2x80x9d is inclusive, meaning and/or; the phrases xe2x80x9cassociated withxe2x80x9d and xe2x80x9cassociated therewith,xe2x80x9d as well as derivatives thereof, may mean to include, be included within, interconnect with, contain, be contained within, connect to or with, couple to or with, be communicable with, cooperate with, interleave, juxtapose, be proximate to, be bound to or with, have, have a property of, or the like; and the term xe2x80x9ccontrollerxe2x80x9d means any device, system or part thereof that controls at least one operation, such a device may be implemented in hardware, firmware or software, or some combination of at least two of the same. It should be noted that the functionality associated with any particular controller may be centralized or distributed, whether locally or remotely. Definitions for certain words and phrases are provided throughout this patent document, those of ordinary skill in the art should understand that in many, if not most instances, such definitions apply to prior, as well as future uses of such defined words and phrases.